"""
3462. 提取至多 K 个元素的最大总和
已解答
中等
相关标签
相关企业
提示
给你一个大小为 n x m 的二维矩阵 grid ，以及一个长度为 n 的整数数组 limits ，和一个整数 k 。你的目标是从矩阵 grid 中提取出 至多 k 个元素，并计算这些元素的最大总和，提取时需满足以下限制：

从 grid 的第 i 行提取的元素数量不超过 limits[i] 。

返回最大总和。



示例 1：

输入：grid = [[1,2],[3,4]], limits = [1,2], k = 2

输出：7

解释：

从第 2 行提取至多 2 个元素，取出 4 和 3 。
至多提取 2 个元素时的最大总和 4 + 3 = 7 。
示例 2：

输入：grid = [[5,3,7],[8,2,6]], limits = [2,2], k = 3

输出：21

解释：

从第 1 行提取至多 2 个元素，取出 7 。
从第 2 行提取至多 2 个元素，取出 8 和 6 。
至多提取 3 个元素时的最大总和 7 + 8 + 6 = 21 。


提示：

n == grid.length == limits.length
m == grid[i].length
1 <= n, m <= 500
0 <= grid[i][j] <= 105
0 <= limits[i] <= m
0 <= k <= min(n * m, sum(limits))
"""


class Solution(object):
    def maxSum(self, grid, limits, k):
        """
        :type grid: List[List[int]]
        :type limits: List[int]
        :type k: int
        :rtype: int
        思路：从grid[i]中取出limits[i]个最大的数，放到dp中，然后再dp中找最大的k个就行了
        """
        dp = []
        for i in range(len(grid)):
            list1 = grid[i]
            list1.sort(reverse=True)
            dp.extend(list1[:limits[i]])
        dp.sort(reverse=True)
        print(type(dp[:k]))
        print(dp[:k])
        return sum(dp[:k])
        # dp.sort()
        # return sum(dp[])


if __name__ == '__main__':
    grid = [[5,3,7],[8,2,6]]
    limits = [2,2]
    k = 3
    print(Solution().maxSum(grid,limits,k))
    #
    # n = 5
    # my_list = [0] * n + [1] * n
    # print(my_list)  # 输出: [0, 0, 0, 0, 0]
    # print(type(my_list))
    # print(type(my_list[0]))
    # print(type([0]))


